package com.huawei;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.lang.*;
import java.io.*;

/**
 * Description: HJ16 购物单
 * 输入：
 * 1000 5
 * 800 2 0
 * 400 5 1
 * 300 5 1
 * 400 3 0
 * 500 2 0
 * 输出：
 * 2200
 *
 * @author weiruibai.vendor
 * Date: 2022/8/15 09:53
 */
public class HJ16 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        int sumMoney = Integer.parseInt(nums[0]);
        int maxBuy = Integer.parseInt(nums[1]);
        Map<Integer, Obj> parentKeyObj = new HashMap<>();
        for (int i = 1; i <= maxBuy; i++) {
            String[] strings = br.readLine().split(" ");
            parentKeyObj.put(i, new Obj(Integer.parseInt(strings[0]), Integer.parseInt(strings[1]), Integer.parseInt(strings[2])));
        }
        int ans = 0;
        for (int i = 1; i <= maxBuy; i++) {
            Set<Integer> hasCalc = new HashSet<>();
            int restBuy = maxBuy;
            int restMoney = sumMoney;
            int tmpAns = 0;
            for (int key = i; key <= maxBuy; key++) {
                Obj obj = parentKeyObj.get(key);
                if (obj.price > restMoney) {
                    // 剩下的钱无法满足
                    continue;
                }
                if (obj.parentKey > 0 && hasCalc.add(obj.parentKey)) {
                    // 有主件且还未计算
                    Obj parent = parentKeyObj.get(obj.parentKey);
                    if ((restBuy < 2 || restMoney < (obj.price + parent.price))) {
                        hasCalc.remove(obj.parentKey);
                        continue;
                    }
                    restBuy--;
                    restMoney -= parent.price;
                    tmpAns += parent.importance * parent.price;
                }
                restMoney -= obj.price;
                tmpAns += obj.importance * obj.price;
                restBuy--;
                ans = Math.max(ans, tmpAns);
            }
        }
        System.out.println(ans);
    }

    private static class Obj {
        public int price; // 价格
        public int importance; // 重要度
        public int parentKey; // 是否📎

        public Obj(int price, int importance, int parentKey) {
            this.price = price;
            this.importance = importance;
            this.parentKey = parentKey;
        }
    }
}
